1304E - 1-Trees and Queries - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define FOR(i,l,r) for(ll i = l; i <= r; ++i)
#define FOD(i,r,l) for(ll i = r; i >= l; --i)
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
const ll inf = 1e18;
const ll N = 1e5;
ll n, h[N + 5], d[N + 5], par[N + 5][30];
vector<ll> dsk[N + 5];


void dfs(ll u, ll p) {
    for(auto v : dsk[u]) {
        if(v != p) {
            par[v][0] = u;
            h[v] = h[u] + 1;
            d[v] = d[u] + 1;
            dfs(v,u);
        }
    }
}
void process() {
    h[1] = 1, dfs(1,0);
    FOR(j,1,25) {
        FOR(i,1,n) par[i][j] = par[par[i][j - 1]][j - 1];
    }
}

ll lca(ll u, ll v) {
    if(h[u] < h[v]) swap(u,v);
    if(h[u] != h[v]) {
        FOD(i,25,0) {
            if(h[par[u][i]] >= h[v]) u = par[u][i];
        }
    }
    if(u == v) return u;
    FOD(i,25,0) {
        if(par[u][i] != par[v][i]) {
            u = par[u][i], v = par[v][i];
        }
    }
    return par[u][0];
}

ll calc(ll a, ll b) {
    ll mid = lca(a,b);
    return d[a] + d[b] - 2 * d[mid];
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    FOR(i,1,n - 1) {
        ll u, v; cin >> u >> v;
        dsk[u].push_back(v);
        dsk[v].push_back(u);
    }
    process();

    ll q; cin >> q;
    while(q--) {
        ll a, b, x, y, k; cin >> x >> y >> a >> b >> k;
        ll w = calc(a,b);
        ll p = min(calc(a,x) + calc(y,b) + 1, calc(a, y) + calc(x,b) + 1);
        ll ans = inf;
        if(w%2 == k%2) ans = min(ans, w);
        if(p%2 == k%2) ans = min(ans, p);

        if(ans <= k) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}
//Jelly1010